/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/spiral-array
   @Language: C++
   @Datetime: 19-04-22 11:16
   */

class Solution {
public:
	/**
	 * @param n: a Integer
	 * @return: a spiral array
	 */
	vector<vector<int>> spiralArray(int n) {
		// write your code here
		vector<vector<int> > vs(n,vector<int>(n,0));
		int direct[4][4]={{0,1,1,-1},{1,0,-1,-1},{0,-1,-1,1},{-1,0,1,1}};
		for(int i=0, j=0, k=0; k<n*n;){
			for(int d=0; d<4; ++d){
				while(i>=0 && i<n && j>=0 && j<n && vs[i][j]==0){
					vs[i][j]=++k;
					i+=direct[d][0], j+=direct[d][1];
				}
				i+=direct[d][2], j+=direct[d][3];
			}
		}
		return vs;
	}
};
